leetcode 322：零钱兑换 |
您所在的位置：网站首页 › 组合总数 leetcode › leetcode 322：零钱兑换 |
|
leetcode 322：零钱兑换
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1示例 2： 输入：coins = [2], amount = 3 输出：-1示例 3： 输入：coins = [1], amount = 0 输出：0提示： 1 int[] dp = new int[amount + 1]; Arrays.fill(dp,amount+1); dp[0] = 0; for(int i = 1; i if(i >= coins[j]){ dp[i] = Math.min(dp[i],dp[i-coins[j]]+1); } } } return dp[amount] == amount+1 ? -1 : dp[amount]; } } 解答成功: 执行耗时:12 ms,击败了81.00% 的Java用户 内存消耗:40.8 MB,击败了37.81% 的Java用户 思路2：递归我们要计算amount所需的最少数量，只需要计算F(S) = F(S-ci) + 1. S表示amont，ci表示每一个硬币值。 但是递归计算会计算很多重复的值，因此可以和思路1一样，使用一个数组存储这些值。 class Solution { public int coinChange(int[] coins, int amount) { return coinChange(coins,amount,new int[amount]); } public int coinChange(int[] coins,int amount,int[] count){ if(amount return 0; } //如果这个值已经计算过 直接返回 if(count[amount-1]!=0){ return count[amount-1]; } //计算amont-硬币值(遍历每一个硬币) 所以的最少硬币 最后加1即可 int min = Integer.MAX_VALUE; for(int coin : coins){ int res = coinChange(coins,amount-coin,count); if(res >= 0 && res |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |